/*

  intersection.c
  
  coverage: gcc -fprofile-arcs -ftest-coverage intersection.c

*/

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

uint8_t array[256];

void clear(void)
{
  int i;
  for( i = 0; i < 256; i++ )
    array[i] = 0;
}

void line(uint8_t from, uint8_t to, uint8_t value)
{
  uint8_t i = from;
  for(;;)
  {
    array[i] |= value;
    if ( i == to )
      break;
    i++;
  }
}

void show(void)
{
  int i = 0;
  for(;;)
  {
    if ( i == 256 )
      break;
    if ( array[i] == 0 ) printf(".");  
    if ( array[i] == 1 ) printf("=");  
    if ( array[i] == 2 ) printf("|");  
    if ( array[i] == 3 ) printf("#");  
    i++;
    if ( (i % 64) == 0 ) printf("\n");
    
  }
  printf("\n");
}

uint8_t a1 = 20;
uint8_t a2 = 40;

int is_array_intersection(void)
{
  int i;
  for( i = 0; i < 256; i++ )
    if ( array[i] >= 3 )
      return 1;
  return 0;
}

#define PLA_SIZE 512
int pla[PLA_SIZE];

void conditioninit(void)
{
  int i;
  for( i = 0; i < PLA_SIZE; i++ )
    pla[i] = 0;
}

void conditionshow(void)
{
  int i, j;
  for( i = 0; i < PLA_SIZE; i++ )
  {
    for( j = 8; j >= 0; j-- )
    {
      printf("%d", (i>>j)&1);
    }
    /*
    if ( pla[i] == 0 )
      printf(" -\n");
    else
      printf(" %d\n", pla[i]);
    */
    
    if ( pla[i] == 0 )
      printf(" 2\n");
    else
      printf(" %d\n", pla[i]-1);
    
  }
}

int conditionpattern(uint8_t b1, uint8_t b2)
{
  int c, p;
  
  p = 0;
  
  c = b1 < a1 ? 1 : 0;
  p <<= 1;
  p |= c;

  c = b1 <= a1 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b1 < a2 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b1 <= a2 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b2 > a1 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b2 >= a1 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b2 > a2 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b2 >= a2 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  c = b1 <= b2 ? 1 : 0;
  p <<= 1;
  p |= c;
  
  return p;
}

int is_math_intersection_original(uint8_t b1, uint8_t b2)
{
  uint8_t c1, c2, c3;
  c1 = b1 <= a2;
  c2 = b2 >= a1;
  c3 = b1 > b2;
  
  if ( c1 && c2 )
    return 1;
  if ( c1 && c3 )
    return 1;
  if ( c2 && c3 )
    return 1;
  
  return 0;
  
}

int is_math_intersection(uint8_t b1, uint8_t b2)
{
  uint8_t c1, c2, c3, tmp;
  c1 = b1 <= a2;
  c2 = b2 >= a1;
  c3 = b1 > b2;
  
  tmp = c1;
  c1 &= c2;
  c2 &= c3;
  c3 &= tmp;
  c1 |= c2;
  c1 |= c3;
  return c1;

/*  
  if ( c1 && c2 )
    return 1;
  if ( c1 && c3 )
    return 1;
  if ( c2 && c3 )
    return 1;
  
  return 0;  
  */
}

uint8_t u8g_is_intersection_math(uint8_t a0, uint8_t a1, uint8_t v0, uint8_t v1)
{
  uint8_t c1, c2, c3, tmp;
  c1 = v0 <= a1;
  c2 = v1 >= a0;
  c3 = v0 > v1;
  
  tmp = c1;
  c1 &= c2;
  c2 &= c3;
  c3 &= tmp;
  c1 |= c2;
  c1 |= c3;
  return c1 & 1;
}

uint8_t u8g_is_intersection_decision_tree(uint8_t a0, uint8_t a1, uint8_t v0, uint8_t v1)
{
  if ( v0 <= a1 )
  {
    if ( v1 >= a0 )
    {
      return 1;
    }
    else
    {
      if ( v0 > v1 )
      {
	return 1;
      }
      else
      {
	return 0;
      }
    }
  }
  else
  {
    if ( v1 >= a0 )
    {
      if ( v0 > v1 )
      {
	return 1;
      }
      else
      {
	return 0;
      }
    }
    else
    {
      return 0;
    }
  }
}



void check(uint8_t b1, uint8_t b2)
{
  int intersection, p;
  clear();
  line(a1, a2, 1);
  line(b1, b2, 2);
  //show();
  intersection = is_array_intersection();
  p = conditionpattern(b1, b2); 
  pla[p] |= intersection+1;
  /*
  if ( p == 0 || p == 7)
    printf("%02x: [%d %d] [%d %d] array_intersection:%d\n", p, a1, a2, b1, b2, intersection);
  */
  if ( is_math_intersection(b1, b2) != intersection)
  {
    printf("%02x: [%d %d] [%d %d] array_intersection:%d != %d failed\n", p, a1, a2, b1, b2, intersection, is_math_intersection(b1, b2));
    exit(0);
  }
  if ( u8g_is_intersection_decision_tree(a1,a2,b1,b2)  != intersection )
  {
    printf("%02x: [%d %d] [%d %d] array_intersection:%d != %d failed\n", p, a1, a2, b1, b2, intersection, u8g_is_intersection_decision_tree(a1,a2,b1,b2));
    exit(0);
  }
  if ( u8g_is_intersection_math(a1,a2,b1,b2)  != intersection )
  {
    printf("%02x: [%d %d] [%d %d] array_intersection:%d != %d failed\n", p, a1, a2, b1, b2, intersection, u8g_is_intersection_math(a1,a2,b1,b2));
    exit(0);
  }
  
}

#define STEP 1
void check_size(uint8_t size)
{
  int i;
  uint8_t b1;
  uint8_t b2;
  b1 = 0;
  for( i = 0; i <= 256; i+=STEP )
  {
    b2 = b1;
    b2 += size;
    check(b1, b2);
    b1 += STEP;
  }
}

void check_all(void)
{
  uint8_t size;
  for( size =0; size < 255; size++ )
  {
    printf("size=%d\n", size);
    check_size(size);
  }
}

void main(void)
{
  assert( u8g_is_intersection_decision_tree(4, 6, 7, 9) == 0 );
  assert( u8g_is_intersection_decision_tree(4, 6, 6, 9) != 0 );
  assert( u8g_is_intersection_decision_tree(6, 9, 4, 6) != 0 );
  assert( u8g_is_intersection_decision_tree(7, 9, 4, 6) == 0 );
  
  conditioninit();
  check_all();
  /*
  check_size(7);
  check_size(17);
  check_size(20);
  check_size(21);
  check_size(37);
  check_size(78);
  */
  //conditionshow();
}


/*
minimized pla from conditionsshow
.i 9
.o 1
.p 2
---1----0 1             b1 <= a2 && b1 > b2
-----1--0 1             b2 >= a1 && b1 > b2
---1-1--- 1             b1 <= a2 && b2 >= a1



pla from conditionsshow
.i 9
.o 1
000000000 0
000000001 2
000000010 2
000000011 2
000000100 2
000000101 2
000000110 2
000000111 2
000001000 1
000001001 2
000001010 2
000001011 2
000001100 2
000001101 2
000001110 2
000001111 2
000010000 2
000010001 2
000010010 2
000010011 2
000010100 2
000010101 2
000010110 2
000010111 2
000011000 1
000011001 2
000011010 1
000011011 2
000011100 2
000011101 2
000011110 1
000011111 0
000100000 1
000100001 2
000100010 2
000100011 2
000100100 2
000100101 2
000100110 2
000100111 2
000101000 1
000101001 2
000101010 2
000101011 2
000101100 2
000101101 2
000101110 2
000101111 2
000110000 2
000110001 2
000110010 2
000110011 2
000110100 2
000110101 2
000110110 2
000110111 2
000111000 1
000111001 2
000111010 2
000111011 2
000111100 2
000111101 2
000111110 2
000111111 1
001000000 2
001000001 2
001000010 2
001000011 2
001000100 2
001000101 2
001000110 2
001000111 2
001001000 2
001001001 2
001001010 2
001001011 2
001001100 2
001001101 2
001001110 2
001001111 2
001010000 2
001010001 2
001010010 2
001010011 2
001010100 2
001010101 2
001010110 2
001010111 2
001011000 2
001011001 2
001011010 2
001011011 2
001011100 2
001011101 2
001011110 2
001011111 2
001100000 1
001100001 2
001100010 2
001100011 2
001100100 2
001100101 2
001100110 2
001100111 2
001101000 1
001101001 2
001101010 2
001101011 2
001101100 2
001101101 2
001101110 2
001101111 2
001110000 2
001110001 2
001110010 2
001110011 2
001110100 2
001110101 2
001110110 2
001110111 2
001111000 1
001111001 1
001111010 2
001111011 1
001111100 2
001111101 2
001111110 2
001111111 1
010000000 2
010000001 2
010000010 2
010000011 2
010000100 2
010000101 2
010000110 2
010000111 2
010001000 2
010001001 2
010001010 2
010001011 2
010001100 2
010001101 2
010001110 2
010001111 2
010010000 2
010010001 2
010010010 2
010010011 2
010010100 2
010010101 2
010010110 2
010010111 2
010011000 2
010011001 2
010011010 2
010011011 2
010011100 2
010011101 2
010011110 2
010011111 2
010100000 2
010100001 2
010100010 2
010100011 2
010100100 2
010100101 2
010100110 2
010100111 2
010101000 2
010101001 2
010101010 2
010101011 2
010101100 2
010101101 2
010101110 2
010101111 2
010110000 2
010110001 2
010110010 2
010110011 2
010110100 2
010110101 2
010110110 2
010110111 2
010111000 2
010111001 2
010111010 2
010111011 2
010111100 2
010111101 2
010111110 2
010111111 2
011000000 2
011000001 2
011000010 2
011000011 2
011000100 2
011000101 2
011000110 2
011000111 2
011001000 2
011001001 2
011001010 2
011001011 2
011001100 2
011001101 2
011001110 2
011001111 2
011010000 2
011010001 2
011010010 2
011010011 2
011010100 2
011010101 2
011010110 2
011010111 2
011011000 2
011011001 2
011011010 2
011011011 2
011011100 2
011011101 2
011011110 2
011011111 2
011100000 1
011100001 2
011100010 2
011100011 2
011100100 2
011100101 2
011100110 2
011100111 2
011101000 2
011101001 2
011101010 2
011101011 2
011101100 2
011101101 2
011101110 2
011101111 2
011110000 2
011110001 2
011110010 2
011110011 2
011110100 2
011110101 2
011110110 2
011110111 2
011111000 2
011111001 1
011111010 2
011111011 1
011111100 2
011111101 2
011111110 2
011111111 1
100000000 2
100000001 2
100000010 2
100000011 2
100000100 2
100000101 2
100000110 2
100000111 2
100001000 2
100001001 2
100001010 2
100001011 2
100001100 2
100001101 2
100001110 2
100001111 2
100010000 2
100010001 2
100010010 2
100010011 2
100010100 2
100010101 2
100010110 2
100010111 2
100011000 2
100011001 2
100011010 2
100011011 2
100011100 2
100011101 2
100011110 2
100011111 2
100100000 2
100100001 2
100100010 2
100100011 2
100100100 2
100100101 2
100100110 2
100100111 2
100101000 2
100101001 2
100101010 2
100101011 2
100101100 2
100101101 2
100101110 2
100101111 2
100110000 2
100110001 2
100110010 2
100110011 2
100110100 2
100110101 2
100110110 2
100110111 2
100111000 2
100111001 2
100111010 2
100111011 2
100111100 2
100111101 2
100111110 2
100111111 2
101000000 2
101000001 2
101000010 2
101000011 2
101000100 2
101000101 2
101000110 2
101000111 2
101001000 2
101001001 2
101001010 2
101001011 2
101001100 2
101001101 2
101001110 2
101001111 2
101010000 2
101010001 2
101010010 2
101010011 2
101010100 2
101010101 2
101010110 2
101010111 2
101011000 2
101011001 2
101011010 2
101011011 2
101011100 2
101011101 2
101011110 2
101011111 2
101100000 2
101100001 2
101100010 2
101100011 2
101100100 2
101100101 2
101100110 2
101100111 2
101101000 2
101101001 2
101101010 2
101101011 2
101101100 2
101101101 2
101101110 2
101101111 2
101110000 2
101110001 2
101110010 2
101110011 2
101110100 2
101110101 2
101110110 2
101110111 2
101111000 2
101111001 2
101111010 2
101111011 2
101111100 2
101111101 2
101111110 2
101111111 2
110000000 2
110000001 2
110000010 2
110000011 2
110000100 2
110000101 2
110000110 2
110000111 2
110001000 2
110001001 2
110001010 2
110001011 2
110001100 2
110001101 2
110001110 2
110001111 2
110010000 2
110010001 2
110010010 2
110010011 2
110010100 2
110010101 2
110010110 2
110010111 2
110011000 2
110011001 2
110011010 2
110011011 2
110011100 2
110011101 2
110011110 2
110011111 2
110100000 2
110100001 2
110100010 2
110100011 2
110100100 2
110100101 2
110100110 2
110100111 2
110101000 2
110101001 2
110101010 2
110101011 2
110101100 2
110101101 2
110101110 2
110101111 2
110110000 2
110110001 2
110110010 2
110110011 2
110110100 2
110110101 2
110110110 2
110110111 2
110111000 2
110111001 2
110111010 2
110111011 2
110111100 2
110111101 2
110111110 2
110111111 2
111000000 2
111000001 2
111000010 2
111000011 2
111000100 2
111000101 2
111000110 2
111000111 2
111001000 2
111001001 2
111001010 2
111001011 2
111001100 2
111001101 2
111001110 2
111001111 2
111010000 2
111010001 2
111010010 2
111010011 2
111010100 2
111010101 2
111010110 2
111010111 2
111011000 2
111011001 2
111011010 2
111011011 2
111011100 2
111011101 2
111011110 2
111011111 2
111100000 1
111100001 0
111100010 2
111100011 2
111100100 2
111100101 2
111100110 2
111100111 2
111101000 2
111101001 1
111101010 2
111101011 2
111101100 2
111101101 2
111101110 2
111101111 2
111110000 2
111110001 2
111110010 2
111110011 2
111110100 2
111110101 2
111110110 2
111110111 2
111111000 2
111111001 1
111111010 2
111111011 1
111111100 2
111111101 2
111111110 2
111111111 1


*/